package com.zy.skip;

import java.util.Optional;
import java.util.Random;

/**
 * __|__ __|__
 * _|_   _|_
 * .---. .---.
 * |___| |___|
 * _\_/_ _\_/_
 * _X_   _X_
 * |   | |   |
 * |___| |___|
 *
 * @Author zhaoyi
 * @date 2020/4/13
 * 跳表实现(默认存正数)
 * https://leetcode-cn.com/problems/design-skiplist/
 * 第一步: 定义跳表节点Node
 * 第二步: 辅助方法
 * ***  1 随机函数,是否添加索引 randomFunction()
 * ***  2 水平方向插入元素 insertLine()
 * ***  3 垂直方向插入元素 insertUpDown()
 * ***  4 创建一个空的索引行 createEmptyLevel()
 * ***  5 定义SkipList的属性head,tail,levels.和构造方法
 * 第三步: 查找对象函数 findEntry(int value, Node startNode)
 * 第四步: 添加函数 add(int num)
 * 第五步: 删除函数 erase(int num)
 */
public class SkipList {


    /**
     * 最上一层的 带头链表
     * createEmptyLevel时会更新
     */
    private Node head;

    /**
     * 最上一层的 最后的节点
     * createEmptyLevel时会更新
     */
    private Node tail;

    /**
     * 索引层级
     */
    private int levels;


    public SkipList() {
        head = new Node(Integer.MIN_VALUE);
        tail = new Node(Integer.MAX_VALUE);
        head.right = tail;
        tail.left = head;
        levels = 0;
    }


    /**
     * 返回target是否存在于跳表中
     */
    public boolean search(int target) {
        return Optional.of(findNode(target, head))
                .map(r -> {
                    return r.getVal() == target;
                }).orElse(false);

    }

    /**
     * 插入一个元素到跳表
     */
    public void add(int num) {
        //1.1 找到要添加的位置（最底层）
        Node source = findNode(num, head);
        Node target = new Node(num);
        //1.2 水平位置插入
        insertLine(source, target);

        //当前层级
        int curLevel = 1;
        while (randomFunction()) {
            //上层没有索引创建新上层索引
            if (curLevel > this.levels) {
                createEmptyLevel();
            }

            //往前找 <- 找到有上层指针的节点
            while (source.up == null) {
                source = source.left;
            }
            //找到上一层的插入位置
            source = source.up;

            //在上一层水平方向插入
            Node newNode = new Node(num);
            insertLine(source, newNode);
            insertUpDown(newNode, target);

            //假如再次往上级插入,建立上下连接的target为本层新加入的节点了
            //而source已经指向了合适的位置
            target = newNode;

            //所在等级+1
            curLevel += 1;

        }


    }

    /**
     * 在跳表中删除一个值，如果 num 不存在，直接返回false. 如果存在多个 num ，删除其中任意一个即可
     * 找到最底层的node将其删除，如果上层有等值的冗余函数， 则向上循环/递归 删除。
     */
    public boolean erase(int num) {
        Node node = findNode(num, head);
        if (node.getVal() != num) {
            return false;
        }
        Node up = null;
        while (node != null) {
            up = node.up;
            //删除
            node.right.left = node.left;
            node.left.right = node.right;

            //指向上级去
            node = up;
        }
        return true;
    }


    /**
     * 定义跳表节点Node
     */
    class Node {
        private int val;
        private Node left, right, up, down;

        public Node(int val) {
            this.val = val;
        }

        public int getVal() {
            return val;
        }
    }


    /**
     * 随机函数,是否添加索引
     * 每次插入元素的时候，都进行一次 50% 概率的判断，如果 true 则向上层添加一个索引，如果 false 就不加了
     */
    private Random random = new Random();

    private boolean randomFunction() {
        return random.nextBoolean();
    }

    /**
     * 水平方向插入元素
     *
     * @param source 再该节点之"后"插入
     * @param target 要插入的节点
     */
    private void insertLine(Node source, Node target) {
        target.left = source;
        target.right = source.right;

        source.right = target;
        target.right.left = target;
    }

    /**
     * 垂直方向插入元素
     *
     * @param source 再该节点之"下"插入
     * @param target 要插入的节点
     */
    private void insertUpDown(Node source, Node target) {
        source.down = target;
        target.up = source;
    }


    /**
     * 创建新的空上层索引
     */
    private void createEmptyLevel() {

        Node newHeader = new Node(Integer.MIN_VALUE);
        Node newTail = new Node(Integer.MAX_VALUE);

        newHeader.right = newTail;
        newTail.left = newHeader;

        //建立连接更新为最上一层的链表
        insertUpDown(newHeader, this.head);
        insertUpDown(newTail, this.tail);
        this.head = newHeader;
        this.tail = newTail;
        this.levels += 1;
        //this.levels++;

    }


    /**
     * 查找对应值的节点,找不到时返回小于value的最大值
     */
    private Node findNode(int value, Node startNode) {
        Node cur = startNode;
        while (cur.right != null && cur.right.getVal() <= value) {
            cur = cur.right;
        }
        if (cur.down != null) {
            return findNode(value, cur.down);
        }
        return cur;
    }

    @Override
    public String toString() {
        return "Skiplist{" +
                "levels=" + levels +
                '}';
    }
}




